The present invention is generally directed to a system and method for providing test data to be applied to integrated circuit chips and chip systems as a means for testing functional logic circuitry present on the chip or in the system. More particularly, the present invention provides a coding method for reducing the amount of storage required for test data. This results in a reduction of the data volume stored in automatic test equipment and also eliminates ineffective patterns from weighted random pattern tests (also known as biased random pattern tests).
As electronic integrated circuit chip components have increased in density (as measured by the number of circuits per square millimeter), the corresponding problem of testing such circuits has also grown. In particular, it is desirous to be able to apply as many effective test patterns as possible to the chip in as small a time as possible so that the number of chips produced (including test) per period of time from a given manufacturing facility is as large as possible without producing defective devices. Accordingly, it is seen that the time that it takes to perform a thorough test is a significant factor in designing the equipment to perform the tests.
In general, there are two different approaches to the generation of test patterns. In deterministic or algorithmitic methods, software decoding techniques are used in test pattern generation software and also in the test equipment to construct a potentially large number of deterministic test patterns from a compact, coded representation. The other approach for generating test patterns is based upon the formation of weighted or biased random patterns. It is this latter approach to which the present application is directed.
Additionally, there are two categories of integrated circuits to which relevant test procedures are generally applied. A first category includes fairly regular circuit structures such as memories, register banks and the like while the second general category includes general functional logic which possesses much more irregularly configured arrangements of circuits and signal lines. The present application is more particularly directed to the testing of logic circuitry. However, the present invention is not limited thereto.
The concept of coded data representations for test pattern storage has been practiced in the past. In particular, diagnostic microcode is a good example of a method which algorithmically generates a typically very large number of test cases to exercise functional logic. Another known example of this type is found in the algorithmic pattern generation for memory arrays. As suggested above, expressing these patterns as stored stimulus/response data is employable, but consumes vast amounts of storage. To overcome this problem, memory test patterns are preferably generated algorithmically by programs. The trick in such cases is to exploit the regularity of the typical memory array test data to construct recursive, looped programs which are then executed in the test equipment (possibly with direct hardware support). The actual test patterns are produced by the executing program. The program itself is a compact, "coded" form representing the particular test data employed.
While such methods are useful for testing memory and array chips, it is difficult to be able to achieve a similar kind of coding efficiency for random logic functions. The data repetitions and recursions that work so well for memory type devices are not well suited for logic tests since the test pattern sequences for random logic seldom show any form of repetitive behavior. This is still generally true even though clock signal lines do exhibit a certain degree of organized structure. However, most other input signals exhibit little apparent regularity. Accordingly, to find effective coding forms for random logic, it is therefore necessary for one to look for other characteristics in test pattern streams.
One property useful in coding is the sparsity of information. For example, if the test pattern stream generated for a specific signal exhibits only relatively few signal changes, then it may be advantageous to store an initial signal value and the number of patterns between changes. Other such "characteristics" and associated codes can be defined. In fact, this is the basis of a "general purpose" test pattern compaction/decompaction method being developed under the label "universal pin electronics". See the article "Initial Physical Implementation Universal Pin Electronics" Autotest Con, 1984, pages 80 through 86 by P. C. Jackson, A. Esser and H. V. Marantz. Universal pin electronics (UPE) uses a repertoire of known data reduction algorithms to encode the information contained in arbitrary test pattern sets. No particular assumptions are made about how the patterns are originally generated. The effectiveness of this algorithm depends on the ability to identify the types of pattern characteristics which are exploited by the algorithms. These characteristics for example might include repetitiveness in clock lines and sparseness in reset lines. Up to a 30-fold data reduction has been reported for such algorithmic methods. The coding algorithms used for data compaction are complemented by hardware in the tester, which decompacts the data in real time. The original test pattern sequences are scrupulously reproduced without adding or subtracting patterns in such schemes.
An entirely different type of coding is exploited in pseudo-random pattern testing. Most of the pseudo-random pattern methods are based on pattern sequences generated with linear feedback shift registers (LFSRs). See for example "An Advanced Fault Isolation System" IEEE Transactions on Computers, 1975, Vol. C-24, pages 49 to 497 by N. Beneowitz, D. F. Calhoun, G. E. Alderson, J. E. Bauer and C. T. Joeckel. A linear feedback shift register typically comprises a serial arrangement of latches wherein specific latch outputs are feed back through Exclusive-OR gates (modulo 2 summers). Such devices are known in the art and are generally configured to cycle through as large a number of output sequences as possible through judicious choices for the feedback paths usually implemented with Exclusive-OR circuits. Such feedback registers (LFSRs) are cycled through a specified number of states to produce the desired test pattern sequence. Only the seed values (initial latch states) and the number of cycles are explicitly stored. In accordance with the present invention, only the seed values and the number of cycle times needed to produce the test pattern are stored. The LFSR is cycled the specified number of times to produce the desired test sequence. The effectiveness of this method depends on a test pattern characteristic that is referred to as "clustering" relative to the number of LFSR cycles. In particular, two test patterns are "close" to one another if they are generated within a few cycles of the LFSR. The success of pseudo-random pattern methods depends on the fact that in general a great many test patterns are clustered closely together near arbitrary seed values. That is to say, close test patterns occur within a reasonable number of LFSR cycles. The dual logarithm of the average number of LFSR cycles between two tests for a given fault is a useful metric which is sometimes referred to as the EAI (equivalent and-invert) value of the fault: EAI=log.sub.2 (average number of LFSR cycles between tests). Faults with small EAI values are usually detected within a few pseudo-random patterns, independent of the LFSR seed or initial value which is chosen.
Most real, complex circuits do nonetheless exhibit a large number of faults having large EAI values, and can therefore not be tested within any reasonable distance from any single seed value. However, the present applicant has perceived that many of these random pattern resistant faults exhibit a different kind of clustering characteristic. In particular, one intuitively expects that any test for such a fault sensitizes a hard to sensitize path in the circuit. By changing a few input values from such a test pattern, one can expect that different branches in the circuit will be connected to the sensitized path, thus, more faults will be detected. In other words, it is expected that tests for multiple faults, each with a possibly high EAI value, differ from each other in only a few bits. The number of bits with different values between code pattern sequences is generally referred to as the Hamming distance. The Hamming distance thus is a useful metric for quantifying test pattern clustering. Therefore, it is seen that test patterns within a short Hamming distance of one another are described in the form: (base vector) XOR (difference vector). The "difference vector" contains only a very few ones and mostly zeroes. It is therefore seen that it is possible to exploit the sparseness of these ones to arrive at a compact data representation for such tests.
The weighted random pattern approach provides an ingenious method for mapping patterns separated by short Hamming distances into shift register output patterns exhibiting short LFSR cycle distances. This occurs because weighted pseudo-random patterns are biased toward suitable base vectors. A weight value defines the strength of biasing. With strong biasing, the pattern generator has a tendency to generate vectors with a short Hamming distance around the chosen base vector within a few LFSR cycles. With a weaker bias, patterns with a low EAI value around the seed are generated. Thus by properly assigning bias to the test inputs to the circuit, one can optimally cover the tests for various different circuit areas with relatively few LFSR cycles. This results in shorter test times and greater facility throughput. An original description of the weighted random pattern testing concept can be found in the article by H. D. Schnurmann et al., titled "The Weighted Random Test-Pattern Generator", in the IEEE Transactions on Computers, Vol. C-24, No. 7, July 1975 at page 695 et seq. A practical implementation used in microchip testing is described in J. A. Waicukauski, et al., "A Method for Generating Weighted Random Test Patterns", IBM Journal of Research & Development, Vol. 33, No. 2, pp. 149-161, March 1989.
However, in its practical implementation, the weighted random pattern test system, just as in other pseudo-random pattern based methods applies test patterns to the circuit regardless of their effectiveness of detecting a previously untested model fault. The number of applied test patterns therefore tends to be significantly larger than that derived from conventional stored pattern methods which only apply relatively effective patterns. The additional patterns are useful because they increase the chances of accidentally detecting unmodeled faults. Thus, better test quality can be achieved than with conventional deterministic tests. This improved quality is however associated with the expense of a potentially significant increase in test application time.
Moreover, there are situations where the increase in test time is not economically justified by the increase in test quality. The economics are dictated by test throughput degradation due to increases in test length and by the expected effectiveness of unmodeled fault detection. It has been ascertained by the applicant herein that when tests are generated based upon the single stuck-at fault model, the weighted random pattern approach has proven to achieve a measurably better accidental delay fault detection rate than deterministic patterns. However, efforts to extend the fault model from single stuck-at faults to critical delay faults has the effect of including a large class of previously unmodeled faults into the set of explicitly modelled test objectives. One must expect therefore that the number of test patterns required to achieve high test coverage against that more stringent fault model will be significantly larger than the number of stuck-at fault test patterns. At the same time, the majority of faults previously discovered accidentally is now modeled, thus reducing the effectiveness of additional patterns. It is thus the case that removing ineffective test patterns from the weighted random pattern tests becomes more attractive. Accordingly, it is this approach which is employed in the present invention. Note also, that with delay testing, the number of test patterns needed for deterministic testing also increases to likely intolerable levels. In other words, it is anticipated that there will be an increasingly strong incentive to explore methodologies that allow the elimination of ineffective test patterns from a weighted random pattern test set while nonetheless retaining the advantages of the reduced explicit data storage volume. These methods can also be useful in other situations where the data transfer band width between the tester and the device under test limits the number of patterns that can be efficiently applied. For example, a service processor which is used for system level test is typically faced with such a problem. Here a small but effective test pattern set generated from a compact data representation would be very helpful.